#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
using namespace std;


int Find_Set(int x);
void Union(int root1,int root2);  
void Make_Set(int n);

int matrix[5][5];
const int vertex = 5;
const int NIL = -1;
const int mc = 1<<20;
int color[vertex];
int parent[vertex];
int dist[vertex];

enum {
    white = 0,
    gray, 
    black
};

void build_graph()
{
    for (int i = 0; i < vertex; i++) 
        for (int j = 0; j < vertex; j++) 
            matrix[i][j] = mc;
        
    for (int i = 0; i < vertex; i++) 
        matrix[i][i] = 0;
    matrix[0][1] = matrix[1][0] = 2;
    matrix[0][4] = matrix[4][0] = 5;
    matrix[1][2] = matrix[2][1] = 4;
    matrix[1][3] = matrix[3][1] = 7;
    matrix[2][3] = matrix[3][2] = 8;
    matrix[3][4] = matrix[4][3] = 6;
    
}

typedef struct edge_weight {
    int u;
    int v;
} ew;

map<int, ew> weight;

void Kruskal()
{
    ew tmp;
    if (! weight.empty()) 
        weight.clear();

    for (int i = 0; i < vertex; i++) {
        for (int j = i+1; j < vertex; j++) {
            if (matrix[i][j] != mc) {
                tmp.u = i;
                tmp.v = j;
                weight.insert(pair<int, ew>(matrix[i][j], tmp));
            }
        }
    }
    Make_Set(vertex);

#if 0
    for (int i = 0; i < vertex; i++) {
        cout << Find_Set(i);
        cout << endl;
    }
   
    return;
#endif

    map<int, ew>::const_iterator it = weight.begin();

#if 0
    for ( ; it != weight.end(); it++) {
        cout << it->first  << "\t" << it->second.u 
            << "\t" << it->second.v << endl;
    }
    return ;
#endif  

    for ( ; it != weight.end(); it++) {
        cout << "weight:" << it->first << "\t";
        cout << "vertex:" << it->second.u << "  father:" 
            << Find_Set(it->second.u) << "\t";
        cout << "vertex:" << it->second.v << "  father:" 
            << Find_Set(it->second.v) << "\t";
        if (Find_Set(it->second.u) != Find_Set(it->second.v)) {
            Union(it->second.u, it->second.v);
            cout << it->first;
        }
        cout << endl;
    }
    cout << endl;
}

void BFS(int s)
{
    queue<int> que;
    for (int i = 0; i < vertex; i++) {
        color[i] = white;
        dist[i] = mc;
        parent[i] = NIL;
    }
    
    color[s] = gray;
    parent[s] = NIL;
    dist[s] = 0;
    que.push(s);
    
    int next;
    while (!que.empty()) {
        next = que.front();
        que.pop();
        cout << next << "\t";
        for (int i = 0; i < vertex; i++) {
            if (matrix[i][next] != mc && color[i] == white) {
                color[i] = gray;
                dist[i] = dist[next] + 1;
                parent[i] = next;
                que.push(i);
            }
        }
        color[next] = black;
    }

    cout << endl;
}

void DFS(int s)
{
    stack<int> st;
    for (int i = 0; i < vertex; i++) {
        color[i] = white;
        parent[i] = NIL;
    }
    
    color[s] = gray;
    parent[s] = NIL;
    st.push(s);
    
    int next;
    while (!st.empty()) {
        next = st.top();
        st.pop();
        cout << next << "\t";
        for (int i = 0; i < vertex; i++) {
            if (matrix[i][next] != mc && color[i] == white) {
                color[i] = gray;
                dist[i] = dist[next] + 1;
                parent[i] = next;
                st.push(i);
            }
        }
        color[next] = black;
    }

    cout << endl;
}

void Prime(int s)
{
    int *key = new int[vertex];
    for (int i = 0; i < vertex; i++) {
        key[i] = mc;
        parent[i] = NIL;
    }
    key[s] = 0;
    // enqueue
    multimap<int, int, less<int> > pri_que;
    for (int i = 0; i < vertex; i++) 
        pri_que.insert(pair<int, int>(key[i], i));
    
    multimap<int, int, less<int> >::iterator it;
    int u;
    int value;
    while (!pri_que.empty()) {
        u = (it = pri_que.begin())->second;
        pri_que.erase(it);
        it = pri_que.begin();
        for (; it != pri_que.end(); it++) {
            int i = it->second;
            if (matrix[u][i] != mc && matrix[u][i] < it->first) {
                value = it->second;
                pri_que.erase(it);
                pri_que.insert(pair<int, int>(matrix[u][i], value));
                parent[it->second] = u;
            }
        }
        cout << u << "\t";
    }
    
    
    delete []key;
}

int main(int argc, char *argv[])
{
    build_graph();
    //BFS(0);
    //DFS(0);
    //Prime(0);
    Kruskal();
    return 0;
}
